#include <iostream>
#include <string>
#include <chrono> // 用于高精度时间测量
using namespace std;

// 方法 1 直接求解——会发现执行时间比预期要慢很多
int getLength1(int n) {
    string s = "";
    for (int i = 1; i <= n; i++) {
        s += to_string(i);
    }
    return s.length();
}

// 方法 2 枚举+计算
int getLength2(int n) {
    int totalLength = 0;
    for (int i = 1; i <= n; i++) {
        int p = i, len = 1;
        while (p >= 10) {
            p /= 10;
            len += 1;
        }
        totalLength += len;
    }
    return totalLength;
}

// 方法 3 数学计算: 分别计算所有数字中个位、十位、百位……的总数，并加入到总和中
// 时间复杂度：优化到O(logN)
int getLength3(int n) {
    int totalLength = 0;
    int b = 1;
    while (n >= b) {
        totalLength += n - b + 1;
        b *= 10;
    }
    return totalLength;
}

int main() {
    // cout << "请输入N: ";
    // int n;
    // cin >> n;
    int n = 20000000;

    auto start = chrono::high_resolution_clock::now();

    int method = 2, totalLength = 0;
    switch (method) {
        case 1:
            totalLength = getLength1(n);
            break;
        case 2:
            totalLength = getLength2(n);
            break;
        case 3:
            totalLength = getLength3(n);
            break;
    }

    auto end = chrono::high_resolution_clock::now();
    chrono::duration<double, milli> elapsed = end - start;

    cout << "使用方法" << method << " N=" << n << " 总长度为 " << totalLength << endl;
    cout << "总时间：" << elapsed.count() << "毫秒" << endl;

    return 0;
}